﻿/*
题目：尾数0连续子数组数量

给定一个数组，请你编写一个函数，返回元素乘积末尾零数量大于等于 x 连续子数组数量

https://www.nowcoder.com/exam/test/77047753/detail?pid=43184608
*/

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <array>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>
#include <random>

using namespace std;

class Solution {
public:
     // 子数组 乘积尾数 0 的个数 -- 0 的个数就取决于 因子 2 和 5 的个数
     // 如果前面已经达到了 0 的个数，那么后面不管怎么乘，都可以满足题意
    int getSubarrayNum(vector<int>& ar, int x) {
        // 计算每个元素拥有的 2、5 因数, 然后求 min(2, 5) 即可
        vector<int> two(ar.size(), 0), five(ar.size(), 0);
        auto factors_count = [](int number, int factor) {
            int cnt = 0;
            while (number % factor == 0) {      // 存在这样的因数
                number /= factor;
                cnt++;
            }
            return cnt;
        };
        for (int i = 0; i < ar.size(); i++) {
            two[i] = factors_count(ar[i], 2);
            five[i] = factors_count(ar[i], 5);
        }

        int res = 0;
        int mod = (int)1e9 + 7;
        for (int l = 0; l < ar.size(); l++) {
            int cur_two = 0, cur_five = 0;
            for (int r = l; r < ar.size(); r++) {
                cur_two += two[r];
                cur_five += five[r];

                if (min(cur_two, cur_five) >= x) {
                    res = (res + (ar.size() - r)) % mod;
                    break;
                }
            }
        }

        return res;
    }
};
